1208E - Let Them Slide - CodeForces Solution

import sys
import io
import os
import traceback
from collections import deque
from itertools import accumulate

BUFSIZE = 8192


class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(io.IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip('\r\n')


def read_int_list():
    return list(map(int, input().split()))


def read_int_tuple():
    return tuple(map(int, input().split()))


def read_int():
    return int(input())



if 'AW' in os.environ.get('COMPUTERNAME', ''):
    test_no = 1
        f = open('inputs')
    def input():
        return f.readline().rstrip("\r\n")

n, w = read_int_tuple()
diff = [0] * (w + 1)

for _ in range(n):
    l, *A = read_int_tuple()
    if l == w:
        for i in range(l):
            diff[i] += A[i]
            diff[i + 1] -= A[i]
        continue

    d = w - l
    if d >= l - 1:
        hi = 0
        for i in range(l - 1):
            if hi < A[i]: hi = A[i]
            diff[i] += hi
            diff[i + 1] -= hi
        if hi < A[l - 1]: hi = A[l - 1]
        diff[l - 1] += hi
        diff[w - l + 1] -= hi
        hi = 0
        for i in range(1, l):
            if hi < A[-i]: hi = A[-i]
            diff[w - i] += hi
            diff[w - i + 1] -= hi
    else:
                                                                        q = deque([(0, -1)])
        for i, x in enumerate(A):
            while q and q[-1][0] <= x: q.pop()
            q.append((A[i], i))
            while i - q[0][1] >= d + 1: q.popleft()
            hi = q[0][0]
            diff[i] += hi
            diff[i + 1] -= hi

                                                                        q = deque([(0, 0)])
        for i in range(1, d + 1):
            x = A[-i]
            while q and q[-1][0] <= x: q.pop()
            q.append((A[-i], i))
            while i - q[0][1] >= d + 1: q.popleft()
            hi = q[0][0]
            diff[w - i] += hi
            diff[w - i + 1] -= hi

diff.pop()
print(*accumulate(diff))